package algorithm;

import conmon.BasicConstant;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {4, 6, 9, 2, 7, 5};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            //分治
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            //整合
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[arr.length];
        int point1 = left;//左边第一个数位置
        int point2 = mid + 1;//右边第一个数位置
        //index  为temp 的下标
        int index = left;
        while (point1 <= mid && point2 <= right) {
            if (arr[point1] <= arr[point2]) {
                temp[index] = arr[point1];
                index++;
                point1++;
            } else {
                temp[index] = arr[point2];
                index++;
                point2++;
            }
        }
        //如果其中一方还有剩余
        //左边还有剩余
        while (point1 <= mid) {
            temp[index++] = arr[point1++];
        }
        //右边还有剩余
        while (point2 <= right) {
            temp[index++] = arr[point2++];
        }
        //将排序好后联临时数组重新赋值给 arr(从 left -> right)
        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }


}
